//
// Description: 987. 二叉树的垂序遍历
// Created by Loading on 2021/7/31.
//

#include <bits/stdc++.h>
#include <Data_Structure_Definition.h>

using namespace std;

vector<vector<int>> verticalTraversal(TreeNode *root) {
    // 最外层 map 按照列序号排序
    // 内层 map 按照行序号排序
    // 最内层 multiset 按顺序存储节点值
    map<int, map<int, multiset<int>>> m;
    // 深度优先遍历
    function<void(TreeNode *, int, int)> dfs = [&](TreeNode *node, int row, int col) {
        m[col][row].insert(node->val);
        if (node->left) {
            dfs(node->left, row + 1, col - 1);
        }
        if (node->right) {
            dfs(node->right, row + 1, col + 1);
        }
    };
    dfs(root, 0, 0);

    vector<vector<int>> res;
    for (auto &it1 : m) {
        vector<int> vec;
        for (auto &it2 : it1.second) {
            for (auto &it3 : it2.second) {
                vec.emplace_back(it3);
            }
        }
        res.emplace_back(vec);
    }

    return res;
}

int main() {
    auto *root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);

    auto res = verticalTraversal(root);
    for (auto &v : res) {
        for (auto &x : v) {
            cout << x << " ";
        }
        cout << endl;
    }
}